package com.learn.acm.one;

import com.learn.acm.po.TreeNode;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个整数 n，生成所有由 1 ... n 为节点所组成的 二叉搜索树 。
 *
 *  
 *
 * 示例：
 *
 * 输入：3
 * 输出：
 * [
 *   [1,null,3,2],
 *   [3,2,null,1],
 *   [3,1,null,null,2],
 *   [2,1,3],
 *   [1,null,2,null,3]
 * ]
 * 解释：
 * 以上的输出对应以下 5 种不同结构的二叉搜索树：
 *
 *    1         3     3      2      1
 *     \       /     /      / \      \
 *      3     2     1      1   3      2
 *     /     /       \                 \
 *    2     1         2                3
 */
public class Solution95 {


    public List<TreeNode> generateTrees(int n) {
        if (n <= 0) return null;

        List<TreeNode> result = createNode(1,n);
        return result;
    }

    private List<TreeNode> createNode(int start,int end) {
        List<TreeNode> allTrees = new ArrayList<>();
        if (start > end) {
            allTrees.add(null);
            return allTrees;
        }
        for (int i = start;i<= end;i++) {

            List<TreeNode> left = createNode(start,i-1);
            List<TreeNode> right = createNode(i+1,end);

            for (TreeNode l : left) {
                for (TreeNode r : right) {
                    TreeNode node = new TreeNode(i,l,r);
                    allTrees.add(node);
                }
            }
        }
        return allTrees;
    }


    public int createTrees(int n) {
        int[] G = new int[n+1];
        G[0] = 1;
        G[1] = 1;
        for (int i =2;i<=n;i++) {
            for (int j = 1;j<=i;j++){
                G[i] += G[i-j] * G[j-1];
            }
        }
        return G[n];
    }

    @Test
    public void testCreateTrees() {
        System.out.println(createTrees(4));
    }
}
